package com.test.daily.leetcode.y2022.m05.day0522.v05;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/22 下午 06:16
 * @version: 1.0
 */
public class Solution {
    public static class Node{
        int value;
        Node left;
        Node right;
        Node parent;
        public Node(int value){
            this.value = value;
        }
    }
    public static Node getSuccessor(Node root){
        if(root == null){
            return  null;
        }
//        Node ans = root.right;
        if(root.right != null){
            return  getLeftestNode(root.right);
        } else {
            Node parent = root.parent;
            while(root == parent.right && parent != null){
                root = parent;
                parent = root.parent;
            }
            return parent;
        }
//        return ans;
    }
    public static Node getLeftestNode(Node head){
        if(head == null){
            return  null;
        }
        Node ans = head;
        while(ans.left != null){
            ans = ans.left;
        }
        return ans;
    }
}
